

class ArrayQueue:
    """
    FIFO queue implementation using a python list as underlying storage
    """
    DEFAULT_CAPACITY = 10

    def __init__(self):
        """
        create empty queue
        """
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._front = 0  # the front of queue
        self._size = 0

    def __len__(self):
        return self._size

    def __str__(self):
        return str(self._data[0:self._size])

    def is_empty(self):
        return self._size == 0

    def first(self):
        """
        Return the element at the front of the queue
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty.")
        return self._data[self._front]

    def dequeue(self):
        """
        Remove and return the first element at the front of the queue.
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty")

        if 0 < self._size < len(self._data)//4:
            self._resize(len(self._data)//2)

        value = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1)%self._size
        self._size -= 1
        return value

    def enqueue(self, value):
        """
        Add an element to back of the queue.
        :return:
        """
        # 队列饱和，扩容2倍
        if self._size == len(self._data):
            self._resize(2 * len(self._data))

        # 计算队尾的位置
        tail = (self._front + self._size) % len(self._data)
        self._data[tail] = value
        self._size += 1

    def _resize(self, length):
        # 缓存旧数据
        old = self._data
        self._data = [None] * length

        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0

